package com.zbcn.algorithm;

public class T15_TrieTree {

    static class TrieNode{
        char data;

        TrieNode[] children;

        boolean isEndingChar = false;

        public TrieNode(char data) {
            this.data = data;
        }
    }

    /**
     * 根节点，存储无意义字符
     */
    private TrieNode root = new TrieNode('/');

    /**
     * 构建 trie 树
     * @param text
     */
    public void insert(char[] text){
        TrieNode p = root;

        for (int i = 0; i < text.length; i++){
            // 算出索引
            int index = text[i] - 'a';
            if (p.children[index] == null){
                p.children[index] = new TrieNode(text[i]);
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
    }


    public boolean find(char[] pattern){
        TrieNode p = root;
        for (int i = 0; i < pattern.length; i ++){
            // 该字符在 trie 树中的位置
            int index = pattern[i] - 'a';
            if (p.children[index] == null){
                // 该字符在trie 树中不存在
                return false;
            }
            p = p.children[index];
        }
        if (p.isEndingChar = false){
            // 该字符串只是前缀子串，不能完全匹配
            return false;
        }
        // text 在trie树中存在
        return true;
    }
}
